#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct v
{
  int a1; // 伤害
  int a2; // 双倍伤害
};

int main()
{
  int N; // 测试次数
  while (N--)
  {
    int n;
    int m;
    cin >> n >> m;

    vector<v> goods(n + 1);
    vector<int> dp(m);
    for (int i = 0; i < n; i++)
    {
      cin >> goods[i].a1 >> goods[i].a2;
    }
    int count = 0;
    // 开始处理0-1背包
    for (int i = 1; i < goods.size(); i++)
    {
      for (int j = m; j > 0; j--)
      {
        if (j >= goods[i].a1)
        {
          dp[m] = max(dp[m], dp[j - goods[i].a1] + goods[i].a1);
          count++;
        }

        else if (j >= goods[i].a2 && j < goods[i].a1)
        {
          dp[m] = max(dp[m], dp[j - goods[i].a2] + goods[i].a2);
          count++;
        }
      }
    }

    cout << count << endl;
  }

  return 0;
}